An FFT butterfly performs the following calculations:Tr=(X2r*Wr)−(X2i*Wi);Ti=(X2i*Wr)−(X2r*Wi);X1r′=X1r+Rr;X1i′=X1i+Ti;X2r′=X1r−Tr;X2i′=X1i−Ti;where: X1r and X2r are respective first and second real coefficients; X1i and X2i are respective first and second imaginary coefficients; Wr is a real twiddle factor; Wi is an imaginary twiddle factor; Tr is a real temporary variable; Ti is an imaginary temporary variable; and X1r′, X2r′, X1i′ and X2i′ are respective updated coefficients. These calculations can be efficiently performed in 4 cycles/butterfly employing: a single multiplier/accumulator; an adder; plus overhead circuits, measured relative to theoretical minimum overhead of 4*(N/2)*log2(N).
Existing techniques, such as the Ceva TeakLite III DSP, have higher overhead partly because they only have enough memory bandwidth to support the data reads and writes. Extra memory bandwidth cycles are required to read new twiddle factors from memory.